A fundamental requirement in digital electronics is a circuit which, depending on the number of highs amongst a second plurality of inputs, selects one of a first plurality of inputs. Such a circuit can be provided to indicate if the number of highs amongst k inputs belongs to any particular subset of the integers {0, 1, . . . , k}.
Examples of such circuits include threshold circuits, which indicate if j or more of k total inputs are high. The threshold function [k,j] is low if there are less than j high inputs within k total inputs, but [k,j] is high if there are j or more high inputs within k total inputs. For example, [10,4] is low for 0 to 3 high inputs, but is high for 4 to 10 high inputs.
Further examples of such circuits include circuits to indicate whether or not an exact number of high inputs are present amongst k total inputs, the circuit outputting a high value only for this exact number of high inputs. This circuit implements the selection function <k,j>, which is defined to be high when k inputs has exactly j high inputs, and low when the number of high inputs in not equal to j. For example, the function <10,4> represents a system with 10 inputs, and is high only when exactly four of these ten inputs are high, otherwise it is low. This function <10,4>, when plotted for a range of different numbers of high inputs, gives a “top-hat” shape—i.e. it is zero if the system has 0 to 3 high inputs, it is 1 if the system has 4 high inputs, and it is zero if the system has 5 to 10 high inputs, where zero represents a low and 1 represents a high.
Such circuits as described above find applications in multiplication, counting, memory control, etc. These circuits often appear on the frequency-limiting paths of systems and can consume large silicon area, and much importance is placed on achieving speed and area improvements in their implementation.
For example, it is instrumental for many applications to have a parallel counter that adds n inputs of the same binary weight together, and produces an output that is a binary representation of the number of high inputs. Such parallel counters (L. Dadda, Some Schemes for Parallel Multipliers, Alta Freq 34: 349-356 (1965); E. E. Swartzlander Jr., Parallel Counters, IEEE Trans. Comput. C-22: 1021-1024 (1973)) are used in circuits performing binary multiplication. There are other applications of a parallel counter, for instance, majority-voting decoders or RSA encoders and decoders. It is important to have an implementation of a parallel counter that achieves a maximal speed.
The following notation is used for logical operations on Boolean variables (such that take one of two values, high and low):                a b denotes the AND of a and b, which is high if a and b are high.        a+b denotes the OR of a and b, which is high if a is high or b is high.        a⊕b denotes the exclusive OR of a and b, which is high if a and b have different values.        a-bar is the complement of a, which is high if a is low.        Σi=a i=b S(i) denotes the OR of a plurality of Boolean expressions, i.e. S(a)+S(a+1)+ . . . +S(b).        